package main

//多元广度优先搜索BFS
func orangesRotting(grid [][]int) int {
	currQueue := [][]int{}
	nextQueue := [][]int{}
	//初始化腐烂队列
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 2 {
				currQueue = append(currQueue, []int{i, j})
			}
		}
	}
	time := 0
	index := 0
	for index < len(currQueue) {
		cell := currQueue[index]
		for i := 0; i < 4; i++ {
			y, x := cell[0]+dy[i], cell[1]+dx[i]
			if x >= 0 && y >= 0 && x < len(grid[0]) && y < len(grid) {
				if grid[y][x] == 1 {
					nextQueue = append(nextQueue, []int{y, x})
					grid[y][x] = 2
				}
			}
		}
		index++
		if index == len(currQueue) {
			if len(nextQueue) == 0 {
				break
			}
			currQueue = nextQueue
			nextQueue = [][]int{}
			index = 0
			time++
		}
	}
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				return -1
			}
		}
	}
	return time
}

func main() {
	grid := [][]int{[]int{0, 1}}
	time := orangesRotting(grid)
	println(time)
}
